"""大数分解 此方法适用于因子较多的大数，或者说在这种情况下此算法才有优势（个人理解，不一定对）"""

import random
import MillerRobin

def gcd(a, b):
    if a < b: raise Exception
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

def fun(k, c, num):
    return (k*k + c)%num


#Floyd算法以后用java写.这里用Brent判圈
def generator(num):
    a = random.randint(1,num - 1)
    b = a
    c = random.randint(1,num - 1)
    count = 1
    n = 2
    while True:
        if count == n:
            b = a
            n = n**2 
        a = fun(a,c,num)
        count += 1
        if b == a:
            return -1
        else:
            result = gcd(num, abs(a - b))
            if result > 1:
                return result

def getfactor(num,item):
    if num == 1:
        return
    if MillerRobin.miller(num):
        item.append(num)
        return
    k = num
    while k == num or k == -1:
        k = generator(num)
    getfactor(k, item)
    getfactor(int(num/k), item)
    



def pollard():
    num = int(input("Please input the number: "))
    item = []
    getfactor(num, item)
    print(item)



